package com.zxy.leetcode._00100_00199._00130_00139;

/**
 * https://leetcode-cn.com/problems/gas-station/submissions/
 *
 * 加油站
 * 在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
 * 你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。
 * 你从其中的一个加油站出发，开始时油箱为空。
 * 如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
 *
 * 说明: 
 * 如果题目有解，该答案即为唯一答案。
 * 输入数组均为非空数组，且长度相同。
 * 输入数组中的元素均为非负数。
 *
 */
public class Test00134 {

    public static void main(String[] args) {
        Test00134 test = new Test00134();
        int[] gas  = {1,2,3,4,5};
        int[] cost = {3,4,5,1,2};

        System.out.println(test.canCompleteCircuit(gas, cost));
    }

    public int canCompleteCircuit(int[] gas, int[] cost) {
        int len = gas.length;

        // 达到当前节点能剩下的油
        for (int i=0; i<len; i++) {
            gas[i] -= cost[i];
        }

        // 根据剩下的油画折线图，类似股价折线图，前面到最低点的这段距离，是耗油的地方，取下一个节点
        // 由于最后结果>=0，所以这个节点走下去，不管是正是负，最后都会是>=0
        int minIndex = -1;
        int min = gas[0];
        int sum = 0;
        for (int i=0; i<len; i++) {
            sum += gas[i];

            if (sum <= min) {
                min = sum;
                minIndex = i;
            }

        }

        // 最终剩下的油是否大于0，小于0肯定白搭
        if (sum < 0) {
            return -1;
        }

        return (minIndex + 1)%len;
    }
}
